package 算法.LeetCode91.每日打卡题目;

import java.util.ArrayList;
import java.util.List;

/**
 * @author:谢君臣
 * @Date:2021/3/1419:18
 * @version:1.0
 * @function:
 * Given a list of integers nums, return the number of pairs i < j such that nums[i] > nums[j] * 3.
 * Constraints
 * n ≤ 100,000 where n is the length of nums
 * Example 1
 * Input
 * nums = [7, 1, 2]
 * Output
 * 2
 * Explanation
 * We have the pairs (7, 1) and (7, 2)
 */

public class day31 {
    public static void main(String[] args) {

    }
    public int solve(int[] nums) {
        int sum = 0;
        List<Integer> arrays = new ArrayList<>();
        for (int i = 0; i < nums.length; i++) {
            int temp = nums[i]*3;
            int index = find(arrays,temp,arrays.size());  // 返回比目标小的最大元素在arrays的下标
            sum += arrays.size()-index;
            int insertIndex = find(arrays,nums[i],index); // 查询当前元素在单调数组的插入位置；
            arrays.add(insertIndex,nums[i]); // 插入元素，维持单调性
        }
        return sum;
    }
    private int find(List<Integer> array,int target,int L){
        if (L<=1)
            return 0;
        int l = 0;
        while (l<L){
            int mid = l +(L-l)/2;
            if (array.get(mid)<=target)
                l = mid+1;
            else
                L = mid;
        }
        return l;
    }

}
